Modern methods for solving problems of planning of task packages execution in multi-stage systems are characterized by the presence of restrictions on their dimension, the impossibility of obtaining guaranteed best results in comparison with fixed packages for different values of the input parameters of tasks. The problem of optimizing the composition of task packages executed in multi-stage systems using the method of branches and borders is solved in the paper. Studies of various ways of forming the order of execution of task packages in multi-stage systems (heuristic rules for ordering task packages in the sequences of their execution on MS devices) have been carried out. The method of ordering packets in the sequence of their execution (a heuristic rule), which minimizes the total time for implementing actions with them on the devices, is defined. The method of ordering the types of tasks, according to which their packages are considered in the procedure of the method of branches and borders, is formulated on the basis of the obtained rule. A mathematical model of the process of implementing actions with packages on the system devices, which provides the calculation of its parameters, has been built. The construction of a method for forming all possible solutions for the composition of task packages for a given number of them has been completed. Decisions on the composition of task packages of different types are interpreted in the procedure of the method of branches and borders in order to build the optimal combination of them. To implement the method of branches and borders, a branching (splitting) procedure is formulated, which assumes the formation of subsets of solutions that include packages of different compositions of tasks of the same type. Expressions for calculating the lower and upper estimates of the values of the optimization criterion for the composition of packages for subsets formed in the branching procedure are constructed. The dropout procedure involves the exclusion of subsets whose lower estimate is not less than the record. To find optimal solutions, a breadth-first search strategy is applied, which provides for the study of all subsets of solutions that include various packages of tasks of the same type obtained as a result of the procedure for splitting subsets of tasks that are not excluded from consideration after the implementation of the dropout procedure. The developed algorithms are implemented programmatically, which allowed to obtain the results of planning the execution of task packages in a multi-stage system, which are on average 30 % better than fixed packages.
The current state with the solution of the problem complex planning of the execution of task packets in multistage system is characterized by the absence of universal methods of forming decisions on the composition of packets, the presence of restrictions on the dimension of the problem and the impossibility of guaranteed obtaining effective solutions for various values of its input parameters, as well the impossibility of registration the condition of the formation of sets from the results. The solution of the task of planning the execution of task packets in multistage systems with the formation of sets of results within the specified deadlines has been realized of authors in article. To solve the planning problem, the generalized function of the system was decomposed into a set of hierarchically interrelated subfunctions. The use of decomposition made it possible to use a hierarchical approach for planning the execution of task packets in multistage systems, which involves defining solutions based on the composition of packets at the top level of the hierarchy and scheduling the execution of packages at the bottom level of the hierarchy. The theory of hierarchical games is used to optimize solutions for the compositions of task packets and schedules for their execution is built, which is a system of criteria at the decision-making levels. Evaluation of the effectiveness of decisions by the composition of packets at the top level of the hierarchy is ensured by the distribution of the results of task execution by packets in accordance with the formed schedule. To evaluate the effectiveness of decisions on the composition of packets, method for ordering the identifiers of the types of sets with registration of the deadlines and a method for distributing the results of the tasks performed by packets has been formulated, which calculates the moments of completion of the formation of sets and delays with their formation relative to the specified deadlines. The studies of planning the process of the executing task packages in multistage systems have been carried out, provided that the sets are formed within specified deadlines. On their basis, conclusions, regarding the dependence of the planning efficiency from the input parameters of the problem, were formulated.
1 - 2 of 2 items